package Lagou.PriorityQueue03;

//堆得基本操作
public class Heap {
    private int[] a = null;
    private int n  =  0;

    //下沉
    public void sink(int i) {
        int j = 0;
        int t = a[i];
        //找到节点的左子节点
        while ((j = (i << 1) + 1) < n) {
            //比较左右子节点谁更大
            if (j < n - 1 && a[j] < a[j + 1]){
                j++;
            }
            if (a[j] > t) {
                a[i] = a[j];
                i = j;
            }else {
                break;
            }
        }
        a[i] = t;
    }

    //上浮
    public void swim(int i) {
        int t = a[i];
        int par = 0;
        //如果存在父节点，找到父节点
        while (i > 0) {
            par = (i - 1) >> 1;
            if (a[par] < t) {
                //如果父节点小于t，则向下移动父节点
                a[i] = a[par];
                i = par;
            }else {
                break;
            }
        }
        a[i] = t;
    }

    //push操作
    public void push(int v) {
        //push先将元素追加到数组尾巴上，然后在执行上浮操作
        a[n++] = v;
        swim(n - 1);
    }

    //pop操作
    public int pop() {
        int ret = a[0];
        a[0] = a[--n];
        sink(0);
        return ret;
    }
    public int size(){
        return n;
    }
}
